// 广度优先 循环方式遍历树状结构
export function treeForeach(tree, func) {
  let node,
    list = [...tree];
  while ((node = list.shift())) {
    func(node);
    node.children && list.push(...node.children);
  }
}

// 深度优先 遍历树状结构
export function treeForeachDeep(tree, func) {
  tree.forEach((data) => {
    func(data);
    data.children && treeForeachDeep(data.children, func); // 遍历子树
  });
}

// 把一维的数组结构转换成树状结构
export function listToTree(list) {
  let info = list.reduce(
    (map, node) => ((map[node.id] = node), (node.children = []), map),
    {}
  );
  return list.filter((node) => {
    info[node.parent] && info[node.parent].children.push(node);
    return !node.parent;
  });
}

// 把树状结构转换成一维数组
export function treeToList(tree, result = [], level = 0) {
  tree.forEach((node) => {
    result.push(node);
    node.level = level + 1;
    node.children && treeToList(node.children, result, level + 1);
  });
  return result;
}

// 筛选结果返回树状结构
export function treeFilter(tree, func) {
  // 使用map复制一下节点，避免修改到原树
  return tree
    .map((node) => ({ ...node }))
    .filter((node) => {
      node.children = node.children && treeFilter(node.children, func);
      return func(node) || (node.children && node.children.length);
    });
}

// 从树状结构中查找某个节点， 返回找到的节点的对象
export function treeFind(tree, func) {
  for (const data of tree) {
    if (func(data)) return data;
    if (data.children) {
      const res = treeFind(data.children, func);
      if (res) return res;
    }
  }
  return null;
}

// 从树状结构中查找某个节点， 返回节点的父级路径
export function treeFindPath(tree, func, path = []) {
  if (!tree) return [];
  for (const data of tree) {
    path.push(data.id);
    if (func(data)) return path;
    if (data.children) {
      const findChildren = treeFindPath(data.children, func, path);
      if (findChildren.length) return findChildren;
    }
    path.pop();
  }
  return [];
}

// 从树状结构中查找某个节点， 返回多条路径路径
export function treeFindPathMany(tree, func, path = [], result = []) {
  for (const data of tree) {
    path.push(data.id);
    func(data) && result.push([...path]);
    data.children && treeFindPath(data.children, func, path, result);
    path.pop();
  }
  return result;
}
